package leetcodecompetition.D372;

import org.junit.jupiter.api.Test;
import tool.s;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @Author: Siantar
 * @Date: 2023-11-19-16:29
 * @Description: 1.0
 */
public class T100110 {
    public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
        int n = heights.length, m = queries.length;
        Integer[] qid = new Integer[m];
        for (int i = 0; i < m; i++) {
            qid[i] = i;
        }
        for (int i = 0; i < m; i++) {
            if (queries[i][0]>queries[i][1]){
                queries[i][0]=queries[i][0]^queries[i][1];
                queries[i][1]=queries[i][0]^queries[i][1];
                queries[i][0]=queries[i][0]^queries[i][1];
            }
        }
        Arrays.sort(qid, (a, b) -> queries[a][1] - queries[b][1]);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int[] res = new int[m];
        int j = 0;
        for (int i = 0; i < n; i++) {
            System.out.println(heights[i]);
            while (!pq.isEmpty() && pq.peek()[0] < heights[i]) {
                int[] p = pq.poll();
                int left = p[0], id = p[1];
                res[id] = i;
                System.out.println("poll " + id + " " + i);
            }
            while (j < m && queries[qid[j]][1] <= i) {
                int left = queries[qid[j]][0], right = queries[qid[j]][1];
                if (left == right || heights[left] < heights[right]) {
                    res[qid[j]] = right;
                    System.out.println("---" + qid[j] + " " + right);
                } else {
                    pq.offer(new int[]{heights[left], qid[j]});
                    System.out.println("offer " + qid[j] + " " + heights[left]);
                }
                j++;
            }
        }
        while (!pq.isEmpty()) {
            int id = pq.poll()[1];
            res[id] = -1;
        }
        return res;
    }

    @Test
    public void test() {
        s.print(leftmostBuildingQueries(
                new int[]{5,3,8,2,6,1,4,6},
                new int[][]{{3, 0}}));
    }
}
